//<p>给你一个 <strong>无重复元素</strong> 的整数数组&nbsp;<code>candidates</code> 和一个目标整数&nbsp;<code>target</code>&nbsp;，找出&nbsp;<code>candidates</code>&nbsp;中可以使数字和为目标数&nbsp;<code>target</code> 的 <em>所有&nbsp;</em><strong>不同组合</strong> ，并以列表形式返回。你可以按 <strong>任意顺序</strong> 返回这些组合。</p>
//
//<p><code>candidates</code> 中的 <strong>同一个</strong> 数字可以 <strong>无限制重复被选取</strong> 。如果至少一个数字的被选数量不同，则两种组合是不同的。&nbsp;</p>
//
//<p>对于给定的输入，保证和为&nbsp;<code>target</code> 的不同组合数少于 <code>150</code> 个。</p>
//
//<p>&nbsp;</p>
//
//<p><strong>示例&nbsp;1：</strong></p>
//
//<pre>
//<strong>输入：</strong>candidates = <code>[2,3,6,7], </code>target = <code>7</code>
//<strong>输出：</strong>[[2,2,3],[7]]
//<strong>解释：</strong>
//2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
//7 也是一个候选， 7 = 7 。
//仅有这两种组合。</pre>
//
//<p><strong>示例&nbsp;2：</strong></p>
//
//<pre>
//<strong>输入: </strong>candidates = [2,3,5]<code>, </code>target = 8
//<strong>输出: </strong>[[2,2,2,2],[2,3,3],[3,5]]</pre>
//
//<p><strong>示例 3：</strong></p>
//
//<pre>
//<strong>输入: </strong>candidates = <code>[2], </code>target = 1
//<strong>输出: </strong>[]
//</pre>
//
//<p>&nbsp;</p>
//
//<p><strong>提示：</strong></p>
//
//<ul>
//	<li><code>1 &lt;= candidates.length &lt;= 30</code></li>
//	<li><code>1 &lt;= candidates[i] &lt;= 200</code></li>
//	<li><code>candidate</code> 中的每个元素都 <strong>互不相同</strong></li>
//	<li><code>1 &lt;= target &lt;= 500</code></li>
//</ul>
//<div><div>Related Topics</div><div><li>数组</li><li>回溯</li></div></div><br><div><li>👍 1949</li><li>👎 0</li></div>

package com.rising.leetcode.editor.cn;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.List;

/**
 * 组合总和
 * @author DY Rising
 * @date 2022-05-11 16:08:48
 */
public class P39_CombinationSum{
    public static void main(String[] args) {
        //测试代码
        Solution solution = new P39_CombinationSum().new Solution();
    }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> rtns = new ArrayList<>();
        if (candidates.length == 0) return rtns;
        //先排序
        Arrays.sort(candidates);
        dfs(candidates, 0, target, new ArrayDeque<>(), rtns);
        return rtns;
    }

    /**
     * 回溯
     * @param candidates
     * @param startIndex
     * @param target
     * @param path
     */
    public void dfs(int[] candidates, int startIndex, int target, Deque<Integer> path, List<List<Integer>> rtns) {
        //target为0，则当前路径结束
        if (target < 0) return;
        //target=0，当前路径满足条件
        if (target == 0) {
            rtns.add(new ArrayList<>(path));
            return;
        }
        for (int i = startIndex; i < candidates.length; i++) {
            //回溯剪枝
            if (target - candidates[i] < 0) break;
            path.add(candidates[i]);
            dfs(candidates, i, target - candidates[i], path, rtns);
            //回溯
            path.removeLast();
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
